package algorithms.sort;

import java.util.Arrays;

public class QuickSort2 {
	public static void sort(int[] array) {
		quickSort(array, 0, array.length - 1);
	}

	private static void quickSort(int[] array, int start, int end) {
		if (start >= end) {
			return;
		} 
		int partition = selectPartition(start, end);
		int mid = array[partition];
		int front = start -1;
		int back = end + 1;
		while (true) {
			while(array[++ front] < mid) {
			}
			
			while(array[ -- back] > mid) {
			}
			if(front >= back) {
				break;
			}
			swap(array, front, back);
		}
		quickSort(array, start, front -1);
		quickSort(array, back + 1, end);
	}

	private static void swap(int[] array, int front, int back) {
		int temp = array[front];
		array[front] = array[back];
		array[back] = temp;
	}

	private static int selectPartition(int start, int end) {
		return (end + start) / 2;
	}

	public static void main(String[] args) {
		int[] array = new int[] {2,4,71,13,6,4,21,2, 8, 5};
		sort(array);
		System.out.println(Arrays.toString(array));
	}
}
